In supervised learning, training data are used to estimate a function that predicts an unknown output based on an input vector of query points. In local learning methods, for a given query point, the function is determined by training points that are “near” the query point. Nearness can be determined by some distance metric.
Examples of local learning methods include nearest-neighbor regression and classification, and locally weighted regression. Two example applications include prediction of future values of a time series based on past values, and detection of whether a particular object is present in an image based on pixel values.
In such problems, the training data set D is a set of pairs D={(x1, y1), . . . , (xM,yM)}⊂×, where X denotes input patterns, e.g., =. Each pair includes an input vector xi, and an output yi. A function ŷ=F(x), which estimates the output from the corresponding input vector is learned from the training data set.
In local learning methods, for each query point xq, the local function F(x) is learned based on only the training data points in the training set that are near the input query point xq. The training points that are near the query point are usually selected from the k nearest points in the training dataset according to the distance metric. Alternatively, the selected training points are less than some distance threshold d from the query point.
The idea the behind local learning methods is that the data can have different characteristics in different parts of the input space, and data that are close to the query point should be the most useful for learning the function to predict the desired output from the given input.
In an example application, it is desired to predict the daily power demand. Different factors can influence the demand load at different times of the year. If the query point corresponds to a summer day, then it can be advantageous to learn a function F( ) based on only the summer days in the training data set.
However, using the k nearest neighbors or all neighbors within some distance d does not always give the best performance.
It is desired to provide a new notion of the local neighborhood along with a method for determining which training points belong to this neighborhood.